//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母组成 
// 
// Related Topics 字符串 动态规划 👍 5134 👎 0


package com.rising.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * 最长回文子串
 * @author DY
 * @date 2022-04-27 17:31:54
 */
public class P5_LongestPalindromicSubstring{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P5_LongestPalindromicSubstring().new Solution();
        System.out.println(solution.longestPalindrome("acbdbbaba"));
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome(String s) {
        if (s == null) return "";
        char[] chars = s.toCharArray();
        int left = 0,len = 1,maxLen = 0 ,leftIndex, rightIndex;
        for (int i = 0; i < chars.length; i++) {
            leftIndex = i - 1; rightIndex = i + 1;
            //向左扩展
            while (leftIndex >= 0 && chars[leftIndex] == chars[i]) {
                leftIndex--;
                len++;
            }
            //向右扩展
            while (rightIndex < chars.length && chars[rightIndex] == chars[i]){
                rightIndex++;
                len++;
            }
            //双向对比
            while (leftIndex >= 0 && rightIndex <chars.length && chars[leftIndex] == chars[rightIndex]) {
                leftIndex--; rightIndex++;
                len = len + 2;
            }
            if (len > maxLen) {
                left = leftIndex;
                maxLen = len;
            }
            len = 1;
        }
        return s.substring(left + 1, left + maxLen + 1);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
